import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=31 lang=java
 *
 * [31] 下一个排列
 */

// @lc code=start
class Solution {
    public void nextPermutation(int[] nums) {
        /**
         * 我硬是记得C++的stl里有个可以全排列的东西的。。
         * 这么想java应该也有
            这题我是看的题解，想法确实挺精妙，自己想的话可能要写很多额外的代码来实现
            感觉还是在考数学
            1. 先从后往前找第一个升序的相邻的（i,j)，nums[i]<nums[j]
            2. 在[j,end)中，从后往前找第一个大于i的k(这个k一定是最小的，因为（i,j)是第一个升序的，说明[j,end)都是降序排列的，所以找到的这个k一定是最小的)
            3  交换i,k。交换之后[j,end)也一定是个逆序的，此时吧顺序弄正即可
            4  如果在1中找不到升序的，说明数组是降序排列，直接逆序整个数组即可
         */
        int len = nums.length;
        if(len==1) return ;
        if(len==2){
            exchange(nums, 0, 1);
            return;
        }
        int i = len-2,j=len-1;
        while(nums[i]>= nums[j] && i!=0){//注意不要让i越界
            i--;
            j--;
        }
        if(i==0 && nums[i]>=nums[j]){//说明是个递减的数组
            Arrays.sort(nums);
            return;
        }
        int k = len-1;
        while(nums[k]<=nums[i] && k!=j){//找k
            k--;
        }
        exchange(nums, i, k);
        //最后都要排序
        Arrays.sort(nums, j, len);//把[j,len)排序
    }
    public void exchange(int[] arr,int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    //最后踩了好多坑才过的。。
}
// @lc code=end

